Graph representations & morphisms.md (1128B)
1 +++ 2 title = 'Graph representations & morphisms' 3 +++ 4 # Graph representations & morphisms 5 Graph representation 6 7 - Adjacency matrix: symmetric. Rows and columns are nodes, cells contain number of edges between nodes 8 - Incidence matrix: rows are vertices, columns are edges. Cell is 1 if the edge is incident on the vertex. 9 - Subgraph: H is subgraph of G if V(H) ⊆ V(G) and E(H) ⊆ E(G) and ∀ (u,v) ∈ E(H) there is u,v ∈ V(H) 10 - in english: a subgraph of G has a subset of vertices and subset of edges of G 11 12 **Homomorphism** is a function ϕ: V(G1) ➝ V(G2) such that for each edge \<u,v> ∈ E(G1) there is an edge <ϕ(u), ϕ(v)> ∈ E(G2) 13 14 **Isomorphism** is a *one-to-one function* ϕ: V(G1) ➝ V(G2) such that for each edge \<u,v> ∈ E(G1) there is an edge \<ϕ(u), ϕ(v)> ∈ E(G2). it has to be unique, one-to-one. 15 16 - in english: two graphs have essentially the same elements with the same organisation. it’s a structure-preserving mapping. 17 - Graphs are not isomorphic if: 18 - |V(G1)| ≠ |V(G2)| 19 - |E(G1)| ≠ |E(G2)| 20 - ordered degree sequence of G1 is different from ordered degree sequence of G2